//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
//
// 示例 1: 
//
// 输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5
// 
//
// 示例 2: 
//
// 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
//输出: 4 
//
// 说明: 
//
// 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 
// Related Topics 堆 分治算法 
// 👍 693 👎 0

package leetcode.editor.cn;

//Java：数组中的第K个最大元素
public class P215KthLargestElementInAnArray {

    /**
     * 思路： 就是从大到小排序，然后取第 n-1 位。 我的执行用时那么久，估计是因为我的排序是 O(n^2)
     *
     * 执行用时： 101 ms , 在所有 Java 提交中击败了 5.04% 的用户 内存消耗： 40.3 MB , 在所有 Java 提交中击败了 30.30% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            sort(nums);
            return nums[k - 1];
        }

        // 从大到小排序
        private void sort(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                int max = i;
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] > nums[max]) {
                        max = j;
                    }
                }
                swap(nums, i, max);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] nums = new int[]{3};
        Solution solution = new P215KthLargestElementInAnArray().new Solution();
        System.out.println(solution.findKthLargest(nums, 1));
        // TO TEST
    }

}